Conventionally, the map matching method used in the navigation apparatus typically finds the vehicle position based on the travel locus of the vehicle calculated by performing the autonomous navigation and by associating the travel locus to the map data. For example, the technique disclosed in a Japanese patent document JP-A-H02-130415 approximates the travel locus of the vehicle by using a fixed length element, and matches the approximation with the map data by selecting, from among the road candidates, one that minimizes the difference of two vectors respectively representing the approximated element and the road candidate. In this case, the road candidates in the map data are also approximated by the fixed length elements. However, road links used in the map matching method represents a center line of the actual road, that is, the center of the road width even when the actual road has bi-directional traffic lanes. Therefore, the following problems are encountered.
FIG. 11A shows an example that road links (link data) of both of a wide road and a narrow road substantially represent the center of the road width of both roads. That is, from the intersection O, link data extends to points C, D and E for representing the wide road, and extends to points A and B for representing the narrow road. The position of the link data is shown in FIG. 11B.
Therefore, when the travel of the vehicle comes from the point A into the intersection O to exit toward the point E, the series of road links for representing the travel can be denoted as AF to FG to GE. However, a portion of the series of road links diverts from the actual road shape and the actual travel locus, the correlation between the road links and the travel locus is deteriorated, thereby leading to a false positioning by the navigation apparatus, which either concludes that the vehicle is not traveling on the road, or that the travel of the vehicle is associated with other road links such as AF to FC.
Further, as shown in FIG. 11C, when a large parking space having a depth exists on one side of the road, a link BD is defined at the center of the entrance of the parking space as shown in FIG. 11D.
Therefore, the road links are traced AB to BD to DE when the vehicle enters the parking space. However, according to the map matching method described above, the road links AB to BC falsely represent the travel of the vehicle due to the smaller vector difference.
The above-described problems are caused by approximating the actual road having an area and a width, that is, a two-dimensional surface by using the one-dimensional elements, i.e., road links. This kind of problem is encountered in various situations, not necessarily limited to the above-described one.
To solve the above-described problem, the road width template is used to tailor the travel locus of the vehicle to be within the range of the template. That is, the travel locus and/or the travel direction of the vehicle is adjusted before performing the map matching. A Japanese patent document JP-A-H10-300492 discloses that the two-dimensional polygon template is used to determine whether the points in the travel locus exist within the road width as shown in FIG. 12A.
However, for the determination of the inclusion of the points in the two-dimensional template, memory areas respectively storing point coordinates of each of the points are required. Further, each of the templates requires different memory areas. Therefore, when the inclusion of one point in the template is performed, the parity number of the lines drawn to the subject point from outside of the template has to be calculated. That is, whether the number of intersection points with the template on the lines drawn to the subject point in total is odd/even has to be determined (see FIG. 12B). The intersection calculation then has to be repeated for the number of times derived by the multiplication of the number of points on the travel locus by the number of templates. This leads to the increased memory resources and thus leads to the cost increase of the navigation apparatus. Further, the increase of the calculation load deteriorates the real-timeness of the navigation, and affects other processing performed in the same CPU.